rly decomposed into sub optimisations. Therefore, if an

ion can be decomposed into piece-wise sub-optimisation

, an optimisation is then an incremental optimisation process.

ns that the current sub-optimisation process is independent from

ous sub-optimisation processes in such an optimisation problem.

equence homology alignment problem is such an optimisation

because the whole homology alignment can be decomposed. The

son for this decomposition likelihood is that almost all metrics

equence homology are linear. Suppose the alignment length of a

gned sequences is N and the score of each aligned pair of residues

d by ݏ௡. The linearity property of the homology measurement

two sequences is shown below,

ܵൌ෍

ݏ௡

ே

௡ୀଵ

(7.1)

linearity property shows that it is possible to decompose this

y alignment for any 1 ൏݉൏݇ and ݉൏݇൏ܰ as shown

here ܵ௠ and ݏ௞ are two decomposed homology alignment scores

egments, one of which has m>1 pairs alignments and the other

air alignment,

ܵൌ෍

ݏ௡൅ݏ௞

௠

௡ୀଵ

ൌܵ௠൅ݏ௞

(7.2)

bove equation is very important as it shows that the calculation

ndependent of the calculation of ܵ௠ or the later optimisation is

ent from the previous optimisations. Therefore, a later homology

t assumes the previous homology alignment has been optimised

ence alignment process. The previous homology alignment only

e whole homology alignment score.

e issues of sequence alignment

ntroducing sequence alignment algorithms, it is better to

nd four key issues which play the key roles in designing a

homology alignment algorithm.